package stack;

import javax.swing.text.Utilities;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 有效括号
 */
public class ValidParentheses {
  public static void main(String[] args) {
    String tmp = "";
    System.out.println(tmp.length());
  }

  public boolean isValid(String s) {
    if (s == null || s.length() == 0) {
      return false;
    }
    Deque<String> stack = new LinkedList<>();
    String leftBrackets = "({[";
    Map<String, String> matching = new HashMap<>();
    matching.put(")", "(");
    matching.put("]", "[");
    matching.put("}", "{");
    for (int i = 0; i < s.length(); ++i) {
      String bracket = s.substring(i, i + 1);
      //遇到左括号直接将其入栈
      if (leftBrackets.contains(bracket)) {
        stack.addFirst(bracket);
      } else {
        //当遍历字符串时遇到右括号，栈顶元素出栈，看是否与该右括号配对
        if (stack.isEmpty()) {
          return false;
        } else if (!matching.get(bracket).equals(stack.removeFirst())) {
          return false;
        }
      }
    }
    if (stack.isEmpty()) {
      return true;
    } else {
      return false;
    }
  }
}
